/**
 * 
 */
package combinatorics.passed;

import java.util.ArrayList;

/**
 * @author xyyi
 *
 */
public class Combination {

	/**
	Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

	For example,
	If n = 4 and k = 2, a solution is:

	[
	[2,4],
	[3,4],
	[2,3],
	[1,2],
	[1,3],
	[1,4],
	]
	 */
	public ArrayList<ArrayList<Integer>> combine(int n, int k) {
		ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
		ArrayList<Integer> buffer = new ArrayList<Integer>();
		combine(n, k, 1, list, buffer);
		return list;
	}

	public void combine(int n, int k, int index,
			ArrayList<ArrayList<Integer>> list, ArrayList<Integer> buffer) {
		if (buffer.size() == k) {
			list.add(new ArrayList<Integer>(buffer));
		} else {
			for (int i = index; i <= n; i++) {
				buffer.add(i);
				combine(n, k, i + 1, list, buffer);
				buffer.remove(buffer.size() - 1);
			}
		}
	}

	public ArrayList<ArrayList<Integer>> combine1(int n, int k) {
		ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
		ArrayList<Integer> buffer = new ArrayList<Integer>();
		combine1(n, k, 1, list, buffer);
		return list;
	}

	public void combine1(int n, int k, int index,
			ArrayList<ArrayList<Integer>> list, ArrayList<Integer> buffer) {
		if (index == n + 1) {
			if (buffer.size() == k) {
				list.add(new ArrayList<Integer>(buffer));
			}
		} else {
			buffer.add(index);
			combine1(n, k, index + 1, list, buffer);
			buffer.remove(buffer.size() - 1);
			combine1(n, k, index + 1, list, buffer);
		}
	}

	public ArrayList<ArrayList<Integer>> combineItr(int n, int k) {
		ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
		if (k == 0)
			return result;
		ArrayList<Integer> buffer = new ArrayList<Integer>(k);
		ArrayList<Integer> goal = new ArrayList<Integer>(k);
		for (int i = 0; i < k; i++) {
			buffer.add(i + 1);
			goal.add(n - (k - 1) + i);
		}
		while (true) {
			result.add(new ArrayList<Integer>(buffer));
			int checker = k - 1;
			while (checker >= 0 && buffer.get(checker) == goal.get(checker))
				checker--;

			if (checker < 0)
				break;
			buffer.set(checker, buffer.get(checker) + 1);

			for (int i = checker + 1; i < k; i++)
				buffer.set(i, buffer.get(i - 1) + 1);
		}

		return result;
	}

	/**
	 * 
	 */
	public Combination() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Combination comb = new Combination();
		int n = 5, k = 3;
		ArrayList<ArrayList<Integer>> list = comb.combineItr(n, k);
		comb.print(list);
	}

	public void print(ArrayList<ArrayList<Integer>> list) {
		for (ArrayList<Integer> arr : list) {
			for (Integer i : arr) {
				System.out.printf("%d,", i);
			}
			System.out.println();
		}
	}

}
